package projectg06.grafosmm;

import static java.lang.System.out;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.TreeSet;

public class Algoritmos {

	public static HashMap<Nodo, Integer> dijkstra(Grafo grafo, Nodo nodo) {
		List<Nodo> subuniverso = grafo.getUniversoNodos();

		HashMap<Nodo, Integer> solucion = new HashMap<Nodo, Integer>();

		// inicializar conjunto solucion
		for (Nodo n : subuniverso) {
			solucion.put(n, new Integer(Integer.MAX_VALUE));
		}
		// paso 0: Hago permanente mi nodo distintivo
		solucion.put(nodo, new Integer(0));
		if (!subuniverso.remove(nodo)) {
			return null;
		}

		while (!subuniverso.isEmpty()) {
			out.println(solucion);
			List<Nodo> adyacentes = grafo.getNodosAdyacentes(nodo);
			int etiquetaPermanente = solucion.get(nodo).intValue();

			// recalcular costos
			for (Nodo unAdyacente : adyacentes) {
				if (subuniverso.contains(unAdyacente)) {
					int etiquetaTemporal = solucion.get(unAdyacente).intValue();
					int costoAdyacente = grafo.getCosto(nodo, unAdyacente);
					if (etiquetaTemporal > etiquetaPermanente + costoAdyacente)
						solucion.put(unAdyacente, new Integer(etiquetaPermanente + costoAdyacente));
				}
			}
			subuniverso.remove(nodo);

			// elijo minima etiqueta temporal y la hago permanente
			boolean primero = true;
			for (Nodo nuevoNodo : subuniverso) {
				if (primero) {
					nodo = nuevoNodo;
					primero = false;
				}
				if (solucion.get(nodo).intValue() > solucion.get(nuevoNodo).intValue())
					nodo = nuevoNodo;
			}
		}
		return solucion;
	}

	/**
	 * Arbol recubridor minimo Se van agregando las aristas de menor peso
	 * 
	 * @param g
	 * @return
	 */
	public static Grafo kruskal(Grafo g) {
		List<Arista> aristas = g.getAristas();
		PriorityQueue queue = new PriorityQueue<Arista>(aristas.size(), new AristaComparator());
		queue.addAll(aristas);
		aristas.clear();
		aristas = null;

		Arista arista;
		Grafo grafo = new Grafo(g.getCantNodos());
		List<Arista> arbolRecubridorMinimo = new ArrayList<Arista>();
		List<Nodo> nodosSinCubrir = g.getUniversoNodos();
		while (queue.size() != 0 && nodosSinCubrir.size() > 0) {
			arista = (Arista) queue.remove();
			out.print(arista);
			boolean nodoRemovido = false;
			nodoRemovido |= nodosSinCubrir.remove(arista.getNodoOrigen());
			nodoRemovido |= nodosSinCubrir.remove(arista.getNodoDestino());
			// si fue removido alguno podemos asegurar que no se forman ciclos
			if (nodoRemovido) {
				out.print(" Agregado ");
				arbolRecubridorMinimo.add(arista);
				grafo.relacionarNodos(arista);
			}
			out.println();
		}
		return grafo;
	}

	public static Grafo prim(Grafo grafo) {
		Grafo grafoSolucion = new Grafo(grafo.getCantNodos());
		Arista arista;
		while ((arista = siguienteArista(grafoSolucion, grafo)) != null) {
			out.println(arista+" Agregado ");
			grafoSolucion.relacionarNodos(arista);
		}
		return grafoSolucion;
	}

	private static Arista siguienteArista(Grafo grafoSolucion, Grafo grafoFuente) {
		List<Arista> aristasPresentes = grafoSolucion.getAristas();
		List<Nodo> nodosConexos = grafoSolucion.getNodosConexos();

		PriorityQueue<Arista> queue = new PriorityQueue<Arista>((int) Math.pow(grafoFuente.getCantNodos(), 2) / 4, new AristaComparator());
		Arista arista = null;

		if (aristasPresentes.size() == 0) {
			queue.addAll(grafoFuente.getAristasIncidentes(grafoFuente.getUniversoNodos().get(0)));
		} else {
			for (Nodo nodo : nodosConexos) {
				queue.addAll(grafoFuente.getAristasIncidentes(nodo));
			}
		}
		boolean aristaValida = false;
		while (!queue.isEmpty() && !aristaValida) {
			arista = queue.remove();
			if (!grafoSolucion.estanRelacionados(arista.getNodoOrigen(), arista.getNodoDestino()) && !grafoSolucion.generaCiclos(arista))
				aristaValida = true;
		}
		if (aristaValida) {
			return arista;
		}
		return null;
	}

	public static void main(String[] args) {
		// ejemplo dijkstra
		// Grafo g = new Grafo(8);
		// g.relacionarNodos(new Arista(0, 3, 5));
		// g.relacionarNodos(new Arista(0, 6, 2));
		// g.relacionarNodos(new Arista(0, 1, 4));
		// g.relacionarNodos(new Arista(3, 4, 2));
		// g.relacionarNodos(new Arista(3, 6, 1));
		// g.relacionarNodos(new Arista(6, 1, 1));
		// g.relacionarNodos(new Arista(1, 2, 5));
		// g.relacionarNodos(new Arista(2, 7, 1));
		// g.relacionarNodos(new Arista(2, 5, 1));
		// g.relacionarNodos(new Arista(5, 7, 2));
		// g.relacionarNodos(new Arista(5, 4, 1));
		// g.relacionarNodos(new Arista(4, 7, 3));
		// out.println(dijkstra(g, new Nodo(0)));

		// ejemplo kruskal
		Grafo g = new Grafo(8);

		g.relacionarNodos(new Arista(0, 1, 1));
		g.relacionarNodos(new Arista(0, 2, 13));
		g.relacionarNodos(new Arista(0, 5, 5));
		g.relacionarNodos(new Arista(0, 3, 6));

		g.relacionarNodos(new Arista(1, 2, 5));
		g.relacionarNodos(new Arista(1, 4, 3));
		g.relacionarNodos(new Arista(1, 3, 14));

		g.relacionarNodos(new Arista(2, 4, 4));
		g.relacionarNodos(new Arista(2, 7, 15));

		g.relacionarNodos(new Arista(3, 6, 9));
		g.relacionarNodos(new Arista(3, 5, 7));

		g.relacionarNodos(new Arista(4, 7, 8));
		g.relacionarNodos(new Arista(4, 6, 11));

		g.relacionarNodos(new Arista(5, 6, 2));
		g.relacionarNodos(new Arista(5, 7, 16));

		g.relacionarNodos(new Arista(6, 7, 10));
		out.println(g);
		out.println("Kruskal");
		out.println(kruskal(g));
		out.println("Prim");
		out.println(prim(g));

	}
}
